//class Solution {
//public:
//	int findDuplicate(vector<int>& nums) {
//		int slow = nums[0], fast = nums[nums[0]];
//		while (slow != fast)
//		{
//			slow = nums[slow];
//			fast = nums[nums[fast]];
//		}
//		slow = nums[0], fast = nums[fast];
//		while (slow != fast)
//		{
//			slow = nums[slow];
//			fast = nums[fast];
//		}
//		return fast;
//	}
//};

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int n = nums.size(), ans = 0;
		int bit_max = 31;
		while (!((n - 1) >> bit_max)) {
			bit_max -= 1;
		}
		for (int bit = 0; bit <= bit_max; ++bit) {
			int x = 0, y = 0;
			for (int i = 0; i < n; ++i) {
				if (nums[i] & (1 << bit)) {
					x += 1;
				}
				if (i >= 1 && (i & (1 << bit))) {
					y += 1;
				}
			}
			if (x > y) {
				ans |= 1 << bit;
			}
		}
		return ans;
	}
};

